1. Field of Invention
This invention relates to methods and systems for generating provably correct code using evolutionary algorithms.
2. Description of Related Art
Evolutionary algorithms are an application of genetic techniques to create and evolve computer programs from a random population of smaller programs. One object of evolutionary algorithms is to generate computer programs automatically without requiring time consuming human generation of the program code.
Evolutionary techniques start by creating an initial population of random programs that are analogous to chromosomes. This initial population is repeatedly evolved through genetic operations into new populations (generations) until a program is evolved which returns the correct solution for the test cases. Programs are individually selected from the population for testing. The fitness of an individual program from the population is determined by running the program on one or more test cases. A measure of an individual program's ability to correctly perform the test cases is used to select the fittest individuals from the population. Individuals are then selected and subjected to mutation and cross-over operations to form another population of programs of the next generation. Individual programs with better fitness are selected with higher probability. This process is repeated until the population contains at least one individual that passes all or sufficiently many of the test cases.